package dp;


import java.util.HashSet;
import java.util.Set;

public class P357 {
    public int countNumbersWithUniqueDigits(int n) {
        return normal(n);
    }


    public int normal(int n) {
        Set<Integer> set = new HashSet<>();
        int total = (int) Math.pow(10, n);
        int count = 0;
        l:
        for (int i = 0; i < total; i++) {
            int tmp = i;
            set.clear();
            while (tmp > 0) {
                if (!set.add(tmp % 10)) {
                    continue l;
                }
                tmp /= 10;
            }
            count++;
        }
        return count;
    }

    int dp(int n) {
        // 重复的数量
        int[] dp = new int[n + 1];
        dp[0] = 0;
        dp[1] = 0;
        for (int i = 2; i <= n; i++) {
            int a = dp[i - 1] * 10;
            int b = (9 * (int) Math.pow(10, i - 2) - dp[i - 1]) * (i - 1);
            dp[i] = a + b;
        }
        return (int) Math.pow(10, n) - dp[n];
    }


    public static void main(String[] args) {
        int result = new P357().countNumbersWithUniqueDigits(3);
        System.out.println(result);
    }
}
